/*************************************************************
 *
 * 图由边的集合及顶点的集合组成。
 *
 * 我们将表示图的边的方法称为邻接表或者邻接表数组。
 *
 * 在图上可以执行两种基础搜索:深度优先搜索和广度优先搜索。
 *
 */

function print(x) {
    console.log(x);
}

(function () {
    function Graph(v) {
        this.vertices = v;
        this.edges = 0;
        this.adj = [];
        for (var i = 0; i < this.vertices; ++i) {
            this.adj[i] = [];
            this.adj[i].push("");
        }
        this.addEdge = addEdge;
        // this.toString = toString;
        this.showGraph = showGraph;
        this.dfs = dfs;
        this.marked = [];
        for (var i = 0; i < this.vertices; ++i) {
            this.marked[i] = false;
        }
    }

    /**
     * 当调用这个函数并传入顶点 A 和 B 时,函数会先查找顶点 A 的邻接表,将顶点 B 添加到列表中,
     * 然后再查找顶点 B 的邻接表,将顶点 A 加入列表。最后,这个函数会将边数加 1。
     * @param v
     * @param w
     */
    function addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }

    /**
     * 打印所有顶点及其相邻顶点列表的方式来显示图
     */
    function showGraph() {
        for (var i = 0; i < this.vertices; ++i) {
            // print(i + "->");
            var tips = [];
            tips.push(i + '>');
            for (var j = 0; j < this.vertices; ++j) {
                if (this.adj[i][j] != undefined)
                // print(this.adj[i][j] + ' ');
                    tips.push(this.adj[i][j] + ' ');
            }
            print(tips.join(""));
        }
    }

    /**
     * 深度优先遍历
     * @param v
     */
    function dfs(v) {
        this.marked[v] = true;
        // 用于输出的 if 语句在这里不是必须的
        if (this.adj[v] != undefined) {
            print("Visited vertex: " + v);
        }
        for (var w in this.adj[v]) {
            if (!this.marked[this.adj[v][w]]) {
                this.dfs(this.adj[v][w]);
            }
        }
    }

    g = new Graph(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.showGraph();

    g.dfs(0);
}());

